package LeetCode.Leet1000_1099.Leet1040_1049.Leet1049;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/6/3 10:09
 * @Description TODO: 方法一    动态规划(0-1背包)  3ms    54.87%
 */
class Solution_1 {
    // 0-1背包问题，尽可能装满背包容量为重量总和的一半的背包
    public int lastStoneWeightII(int[] stones) {
        // 石头总重量
        int n = 0;
        for (int i = 0; i < stones.length; i++) {
            n += stones[i];
        }
        // 背包容量
        int capacity = n / 2;

        // dp[i][j]：背包容量为j，装前i个石头能装石头的最大重量
        int[][] dp = new int[stones.length][capacity + 1];

        // 初始化
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = j >= stones[0] ? stones[0] : 0;
        }

        // 动态规划
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < stones[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], stones[i] + dp[i - 1][j - stones[i]]);
                }
            }
        }

        return n - 2 * dp[stones.length - 1][capacity];
    }
}
